package com.easy;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Lxk on 2020/2/29.
 */
public class Solution204 {

    public int countPrimes(int n) {
        if (n < 2) {
            return 0;
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i < n; i++) {
            if (primes.size() == 0) {
                primes.add(i);
            } else {
                boolean isPrime = true;
                for (int k = 0; k < primes.size() && primes.get(k) <= Math.sqrt(i); k++) {
                    if (i % primes.get(k) == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {
                    primes.add(i);
                }
            }
        }
        return primes.size();
    }

    public static void main(String[] args) {
        Solution204 solution204 = new Solution204();
        System.out.println(solution204.countPrimes(10));
    }

}
